// Stack.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <array>
#include <stack>
#include <iostream>

using namespace std;

template<size_t N>
int largestRectangleArea(array<int, N> &height) 
{
    stack<int> s;
    int result = 0;
    for (int i = 0; i < height.size(); ) 
    {
        if (s.empty() || height[i] > height[s.top()])
        {
            s.push(i++);
        }
        else 
        {
            int tmp = s.top();
            s.pop();
            result = max(result, height[tmp] * (s.empty() ? i : i - s.top() - 1));
        }
    }

    return result;
}

void testLargetsRectangleArea()
{
    array<int, 7> data = {2, 4, 5, 6, 2, 3, 0};
    auto ret = largestRectangleArea(data);
    cout << "largestRectangleArea is " << ret << endl;
}

int _tmain(int argc, _TCHAR* argv[])
{
    testLargetsRectangleArea();
    cin.get();
	return 0;
}

